package com.ljy.my_study.leetcode.交错字符串;

/**
 * @author lijunying
 * @date 2021/11/16 11:45
 */
public class TestMain2 {

    public static void main(String[] args) {
//        String s1=
//                "abababababababababababababababababababababababababababababababababababababababababababababababababbb";
//        String s2=
//                "babababababababababababababababababababababababababababababababababababababababababababababababaaaba";
//        String s3=
//                "abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababbb";
//        String s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
//        System.out.println(new TestMain2().isInterleave(s1,s2,s3));
//        String s1 = "aadbcc", s2 = "bbca", s3 = "aadbbbaccc";
//        System.out.println(new TestMain2().isInterleave(s1,s2,s3));
//        String s1="aa";
//        String s2="ab";
//        String s3="abaa";
//        System.out.println(new TestMain2().isInterleave(s1,s2,s3));
//        String s1="aa";
//        String s2="ab";
//        String s3="abaa";
        String s1="ab";
        String s2="bc";
        String s3="bbac";
        System.out.println(new TestMain2().isInterleave(s1,s2,s3));
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int len1=s1.length();
        int len2=s2.length();
        int len3=s3.length();
        if(len1+len2!=len3){
            return false;
        }
        boolean[][] dp=new boolean[len1+1][len2+1];
        dp[0][0]=true;
        for(int i=0;i<=len1;i++){
            for(int j=0;j<=len2;j++){
                if(i>0){
                    dp[i][j]=dp[i][j]||(s1.charAt(i-1)==s3.charAt(i+j-1)&&dp[i-1][j]);
                }
                if(j>0){
                    dp[i][j]=dp[i][j]||(s2.charAt(j-1)==s3.charAt(i+j-1)&&dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
}
